Multiprocessing systems such as those found in computers, control systems, switching systems and graphics controllers, require a way for different processes to communicate and to share common information. These processes may be different programs running on physically separate processors, different users in a timeshared or multithreaded computer system, or different program fragments in a distributed computer system. Information sharing is often accomplished through the use of globally shared data, either in a common memory or distributed in several locations.
Whenever concurrent processors share common data, there is a possibility that they will interfere with each other when they access the common data. The interference can take several forms: one process may be delayed by another through contention for access to the data, the data may be corrupted through timing anomalies between reads and writes from different processes, or two processes may deadlock, with each waiting for the other to update the common data. In order avoid such interference, it is crucial for the system to include a means of access control to arbitrate between processes which share data.
A number of techniques have been developed in operating system theory to control access to common resources, including locks, semaphores, monitors and serializers. Of these techniques, only locking can be applied without significantly changing the timing of other processes. Locking is important in multiple processor systems and distributed systems, and where processes have been designed independently of each other. Locking is a technique in which each process requests exclusive access to a block of data when interference is likely to cause problems. No other process may access the block of data until the original requestor releases it. Locks may be of different types. For example, a system may include a write lock to prevent any other process from reading data until the lock holder updates it and a read lock to prevent any other process from updating a block of data while the lock holder reads it, while allowing other processes to read the data. Locks may also be used to selectively grant or deny access to specific processes.
In the past, software approaches to locking control have required a number of processor instructions (typically 10 to 25) to check for locks on every memory access. It is apparent that such a locking scheme presents a significant penalty in system operating speed. Hardware solutions to the mutual exclusion problem are discussed by M. Raynal in Algorithms for Mutual Exclusion, the MIT Press, Chapter 3, pages 39-44. All known locking techniques have resulted in a time penalty to perform the locking function.
Content-addressable memories have been used in connection with mapping of memory systems. See for example, T. Kohonen, Content Addressable Memories, Springer Verlag, New York, 1980, pp 241-261; U.S. Pat. No. 3,755,791 issued Aug. 28, 1973 to Arzubi; and U.S. Pat. No. 3,848,234 issued Nov. 12, 1974 to MacDonald. However, none of these references relate to controlling access to locked segments of a shared memory.
It is a general object of the present invention to provide improved multiprocessor, timeshared and distributed computer systems.
It is another object of the present invention to provide a locking circuit for controlling access to shared memory.
It is a further object of the present invention to provide an extremely fast locking circuit for controlling access to shared memory.
It is yet another object of the present invention to provide a locking circuit for controlling access to shared memory wherein lock checking is performed simultaneously with a memory access cycle.